This invention relates to the deduction of a functional relationship between an input and an output and, more particularly, to the optimization of one or more generalizers of a physical system to deduce outputs from inputs. This invention was made with government support under Contract No. W-7405-ENG-36 awarded by the U.S. Department of Energy. The government has certain rights in the invention.
The fundamental problem in supervised machine learning is to infer a "parent" function f taking input values x to output values y, given a known training set of x-y pairs which are samples of f. Applications of this problem occur in, e.g., learning to read hand-written characters, learning to recognize spoken speech, and deducing a 3-D amino acid structure from an arbitrary amino acid sequence. As used herein, any algorithm that takes in a training set of values and outputs a guess of the function that generated the training set is a "generalizer." The generalizer uses the training set to create a function h, which is its guess for function f; the generalizer's guess for the output corresponding to an input question q is given by h(q).
Some examples of generalizers are back-propagated neural nets (D. E. Rumelhart et al., Explorations in the Microstructure of Cognition, Vol. I and II, MIT Press (Cambridge, Mass. 1986)); classifier systems (J. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press (Ann Arbor, Mich. 1975)); and various uses of the minimum description length principle (J. Rissanen, "Stochastic Complexity and Modeling," 14 The Annals of Statistics, pp. 1080-1100 (1986)). Other important examples are memory-based reasoning schemes (C. Stanfill, "Toward Memory-based Reasoning," 29 Communications of the ACM, pp. 1213-1228 (1986); regularization theory (T. Poggio et al., "MIT Progress in Understanding Images," in L. Bauman (Ed.), Proceedings of the Image Understanding Workshop, pp. 111-129 (McLean, Va. 1988); and similar schemes for overt surface fitting of a parent function to the learning set (e.g., D. Wolpert, "A Benchmark for How Well Neural Nets Generalize," 61 Biological Cybernetics, pp. 303-313 (1989)).
For any real-world learning set .theta., there are always many possible generalizers {G.sub.j } that might be used to extrapolate from .theta.. The implicit problem is how to address this multiplicity of possible generalizers. Most algorithm schemes for addressing this problem, including, in particular, nonparametric statistics techniques like cross-validation, generalized cross-validation, and bootstrapping, are winner-take-all strategies. These schemes can be viewed as mappings that take an arbitrary generalizer and learning set as input, and give as output an estimate of the average generalizing accuracy of that generalizer for the unknown parent function that generated the learning set. To exploit such a mapping, one simply picks that G.epsilon.{G.sub.j }, which, together with .theta., has the highest estimated generalization accuracy according to the mapping, and then uses that G to generalize from .theta..
Thus, conventional strategies provide only a means of estimating the generalization accuracy of a single generalizer. It would be desirable to improve the accuracy of the generalization rather than just estimate the accuracies of some generalizers The present invention provides improved accuracy in the output guesses by introducing a second generalizer that is "fed" by the first generalizer or generalizers and which infers a function to improve the output guess of the first generalizer or generalizers. If one generalizer is used, the second generalizer either infers an error for correcting the output guess of that generalizer or infers a correct guess. If several generalizers are used, the second generalizer infers a function for combining the outputs from the first generalizers to minimize error in the resulting combined guess, or infers a function relating the output guesses to the error for some single generalizer.
Accordingly, one object of the present invention is to obtain improved guesses of outputs from inputs for the physical system.
Another object of the present invention is to combine generalizers to provide improved accuracy in the guess for the output of the physical system corresponding to a given input value "question".
Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.